package com.chapter10;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BinaryTree extends Tree{

	public BinaryTree() {
		super();
	}

	public BinaryTree(Tnode root) {
		super(root);
	}
	
	
	public Tnode getBTfromInandLevel(int[] in, int[] level)
	{
		Map<Integer,Integer> inMap=new HashMap<Integer,Integer>();
		Map<Integer,Integer> lMap=new HashMap<Integer,Integer>();
		for(int i=0;i<in.length;i++){
			inMap.put(in[i], i);
			lMap.put(level[i], i);
		}
		Tnode root=new Tnode(level[0]);
		int nP=0;// increments when left or right node is absent.
		List<NodeInfo> q=new ArrayList<NodeInfo>();
		NodeInfo nodeInfo = new NodeInfo(root,in.length-1,0,inMap.get(level[0]));
		q.add(nodeInfo);
		NodeInfo current=nodeInfo;

		while(true){
			current=q.remove(0);
			int indexLeft=2*lMap.get(current.node.value) +1-nP;
			if(indexLeft>=in.length)
				break;
			indexLeft=inMap.get(level[indexLeft]);
			if(indexLeft<=current.index && indexLeft>=current.min){
				current.node.left=new Tnode(in[indexLeft]);
				current.node.left.parent=current.node;
				current.node.leftNodes++;
				incrementNodeCount(current.node);
				q.add(new NodeInfo(current.node.left,current.index-1,current.min,indexLeft));
			}
			else
				nP++;
			int indexRight=2*lMap.get(current.node.value) +2-nP;
			if(indexRight>=in.length)
				break;
			indexRight=inMap.get(level[indexRight]);
			if(indexRight>=current.index && indexRight<=current.max){
				current.node.right=new Tnode(in[indexRight]);
				current.node.right.parent=current.node;
				current.node.rightNodes++;
				incrementNodeCount(current.node);
				q.add(new NodeInfo(current.node.right,current.max,current.index+1,indexRight));
			}
			else
				nP++;
		}
		return root;
	}

	
}
